package com.taotao.job.core.util;

import com.google.common.base.Preconditions;
import com.google.common.graph.*;

import java.util.*;

/**
 * 有向无环图工具类
 *
 * @author fanbeibei
 * @version 1.0
 * @date 2020/11/13 13:53
 */
public class DAGUtils {

    private DAGUtils() {

    }


    /**
     * @param expectedNodeCount 预期节点数
     * @param <T>
     * @return
     */
    public static <T> MutableGraph<T> createEmptyDAG(int expectedNodeCount) {

        return GraphBuilder
                //指定为有向图
                .directed()
                //节点按插入顺序输出
                //(还可以取值无序unordered()、节点类型的自然顺序natural())
                .nodeOrder(ElementOrder.<T>insertion())
                //预期节点数
                .expectedNodeCount(expectedNodeCount)
                //是否允许自环
                .allowsSelfLoops(false)
                .build();
    }


    public static <T> MutableGraph<T> createEmptyDAG() {

        return createEmptyDAG(20);
    }


    /**
     * 复制一份图
     *
     * @param graph
     * @param <T>
     * @return
     */
    public static <T> MutableGraph<T> copyGraph(MutableGraph<T> graph) {
        Preconditions.checkArgument(null != graph, "graph is null");
        return Graphs.copyOf(graph);
    }


    /**
     * 检查图中是否存在环
     *
     * @param graph
     * @param <T>
     * @return
     */
    public static <T> boolean hasLoop(MutableGraph<T> graph) {
        Preconditions.checkArgument(null != graph, "graph is null");

        return Graphs.hasCycle(graph);
    }


    /**
     * 找环路径
     *
     * @param graph 图
     * @param node  环中包含的节点.为空则表示从整个图中找环,否则表示仅寻找包含节点的环
     */
    public static <T> List<String> getLoop(MutableGraph<T> graph, T node) {
        Preconditions.checkArgument(null != graph, "graph is null");

        MutableGraph<T> loopGraph = getLoopGraph(graph, node);


        Set<T> loopNodes = loopGraph.nodes();
        if (null == loopNodes || 0 == loopNodes.size()) {
            return Collections.emptyList();
        } else {
            loopNodes = new HashSet<>(loopNodes);
        }


        List<String> loopInfoList = new ArrayList<>();


        while (loopNodes.size() > 0) {
            Set<T> reachNodes = Collections.emptySet();
            for (T n : loopNodes) {
                reachNodes = Graphs.reachableNodes(loopGraph, n);
                loopInfoList.add(Graphs.inducedSubgraph(loopGraph, reachNodes).edges().toString());
                break;
            }

            //删掉环节点，继续找环
            loopNodes.removeAll(reachNodes);
        }

        return loopInfoList;
    }


    /**
     * 获取只包含环的节点构成的图,去掉环以外的节点
     *
     * @param graph0
     * @param node
     * @param <T>
     * @return
     */
    private static <T> MutableGraph<T> getLoopGraph(MutableGraph<T> graph0, T node) {
        Preconditions.checkArgument(null != graph0, "graph is null");

        //不影响原来的图
        MutableGraph<T> graph = copyGraph(graph0);


        MutableGraph<T> subgraph = null;
        List<T> subNodeList = null;
        if (null != node) {
            //获取可达节点
            Set<T> reachNodes = Graphs.reachableNodes(graph, node);
            if (null == reachNodes || 0 == reachNodes.size()) {
                return createEmptyDAG(1);
            }

            HashSet<T> subNodes = new HashSet<>(reachNodes);
            subgraph = Graphs.inducedSubgraph(graph, subNodes);
            subNodeList = new ArrayList<>(subNodes);
        } else {
            subgraph = graph;
            subNodeList = new ArrayList<>(graph.nodes());
        }


        //减掉没有入度或没有出度的节点，剩下的就是环
        boolean hasExNode = false;
        do {
            hasExNode = false;
            for (Iterator<T> iter = subNodeList.iterator(); iter.hasNext(); ) {
                T n = iter.next();
                //减掉没有入度或没有出度的节点
                if (0 == subgraph.inDegree(n) || 0 == subgraph.outDegree(n)) {
                    iter.remove();
                    subgraph.removeNode(n);
                    hasExNode = true;
                    break;
                }
            }
        } while (hasExNode);

        return subgraph;
    }


    /**
     * 获取顶层节点
     *
     * @param graph0
     * @param <T>
     * @return
     */
    public static <T> Set<T> getTopNodes(MutableGraph<T> graph0) {
        Preconditions.checkArgument(null != graph0);
        Set<T> nodes = graph0.nodes();
        if (null == nodes || 0 == nodes.size()) {
            return Collections.emptySet();
        }

        Set<T> topNodes = new HashSet<>();
        for (T n : nodes) {
            if (isTopNode(graph0, n)) {
                topNodes.add(n);
            }
        }


        return topNodes;

    }


    /**
     * 获取底层节点
     *
     * @param graph0
     * @param <T>
     * @return
     */
    public static <T> Set<T> getBottomNodes(MutableGraph<T> graph0) {
        Preconditions.checkArgument(null != graph0);

        Set<T> nodes = graph0.nodes();
        if (null == nodes || 0 == nodes.size()) {
            return Collections.emptySet();
        }

        Set<T> bottomNodes = new HashSet<>();
        for (T n : nodes) {
            if (isBottomNode(graph0, n)) {
                bottomNodes.add(n);
            }
        }


        return bottomNodes;

    }

    /**
     * 获取孤立节点
     *
     * @param graph0
     * @param <T>
     * @return
     */
    public static <T> Set<T> getStandAloneNodes(MutableGraph<T> graph0) {
        Preconditions.checkArgument(null != graph0);

        Set<T> nodes = graph0.nodes();
        if (null == nodes || 0 == nodes.size()) {
            return Collections.emptySet();
        }

        Set<T> standAloneNodes = new HashSet<>();
        for (T n : nodes) {
            if (isStandAloneNode(graph0, n)) {
                standAloneNodes.add(n);
            }
        }


        return standAloneNodes;

    }


    /**
     * 是否顶层节点
     *
     * @param node
     * @return
     */
    public static <T> boolean isTopNode(MutableGraph<T> graph0, T node) {
        Preconditions.checkArgument(null != graph0);
        Preconditions.checkArgument(null != node);

        if (!graph0.nodes().contains(node)) {
            return false;
        }


        try {
            //入度为0，出度大于0为顶层节点
            return graph0.inDegree(node) == 0 && graph0.outDegree(node) > 0;
        } catch (IllegalArgumentException e) {
            return false;
        }
    }


    /**
     * 是否底层节点
     *
     * @param node
     * @return
     */
    public static <T> boolean isBottomNode(MutableGraph<T> graph0, T node) {

        Preconditions.checkArgument(null != graph0);
        Preconditions.checkArgument(null != node);

        if (!graph0.nodes().contains(node)) {
            return false;
        }

        try {
            //入度大于0，出度为0为底层节点
            return graph0.inDegree(node) > 0 && graph0.outDegree(node) == 0;
        } catch (IllegalArgumentException e) {
            return false;
        }
    }


    /**
     * 是否孤立节点
     *
     * @param node
     * @return
     */
    public static <T> boolean isStandAloneNode(MutableGraph<T> graph0, T node) {

        Preconditions.checkArgument(null != graph0);
        Preconditions.checkArgument(null != node);
        if (graph0.nodes().contains(node)) {
            return false;
        }
        try {
            return graph0.inDegree(node) == 0 && graph0.outDegree(node) == 0;
        } catch (IllegalArgumentException e) {
            return true;
        }
    }


    /**
     * 依据给点节点获取子图
     *
     * @param graph0
     * @param subNodes
     * @param <T>
     * @return
     */
    public static <T> MutableGraph<T> getSubDAG(MutableGraph<T> graph0, Set<T> subNodes) {
        Preconditions.checkArgument(null != graph0);
        Preconditions.checkArgument(null != subNodes && subNodes.size() > 0);

        return Graphs.inducedSubgraph(graph0, subNodes);
    }


    /**
     * 获取节点可达节点
     *
     * @param graph0
     * @param node
     * @param <T>
     * @return
     */
    public static <T> Set<T> reachableNodes(Graph<T> graph0, T node) {
        Preconditions.checkArgument(null != graph0);
        Preconditions.checkArgument(null != node);

        return Graphs.reachableNodes(graph0, node);
    }

    /**
     * 获取反向图
     *
     * @param graph0
     * @return
     */
    public static <T> Graph<T> transpose(MutableGraph<T> graph0) {
        Preconditions.checkArgument(null != graph0);

        return Graphs.transpose(graph0);
    }


    /**
     * 获取有向图中互不连接的子图
     *
     * @param graph0
     * @param <T>
     * @return
     */
    public static <T> List<Graph<T>> divideGraph(MutableGraph<T> graph0) {
        Preconditions.checkArgument(null != graph0);


        Set<T> nodes0 = graph0.nodes();
        if (null == nodes0 || 0 == nodes0.size()) {
            return Collections.emptyList();
        }


        MutableGraph<T> unDirectGraph = createUndirectGraph();
        for (EndpointPair<T> e : graph0.edges()) {
            unDirectGraph.putEdge(e.nodeU(), e.nodeV());
        }

        Set<T> nodes = new HashSet<>(unDirectGraph.nodes());

        List<Graph<T>> subGraphs = new ArrayList<>();
        while (nodes.size() > 0) {

            for (T n : nodes) {
                Set<T> reachableNodes = Graphs.reachableNodes(unDirectGraph, n);
                if (null != reachableNodes && reachableNodes.size() > 0) {
                    subGraphs.add(Graphs.inducedSubgraph(graph0, reachableNodes));
                    nodes.removeAll(reachableNodes);
                } else {

                    MutableGraph<T> subGraph = createEmptyDAG(1);
                    subGraph.addNode(n);
                    subGraphs.add(subGraph);

                    nodes.remove(n);
                }

                break;
            }

        }


        return subGraphs;

    }


    private static <T> MutableGraph<T> createUndirectGraph() {
        return GraphBuilder
                //指定为无向图
                .undirected()
                //节点按插入顺序输出
                //(还可以取值无序unordered()、节点类型的自然顺序natural())
                .nodeOrder(ElementOrder.<T>insertion())
                //预期节点数
                .expectedNodeCount(20)
                //是否允许自环
                .allowsSelfLoops(false)
                .build();
    }


    public static void main(String[] args) {
        MutableGraph<Integer> dag = createEmptyDAG();

        dag.putEdge(2, 1);

        dag.putEdge(2, 3);

        dag.putEdge(4, 3);

        dag.putEdge(5, 6);


        dag.addNode(7);
        dag.addNode(8);
        dag.addNode(9);


        List<Graph<Integer>> subGraphs = divideGraph(dag);
        System.out.println(subGraphs);


    }


}
